#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef double db;

#define in read()
#define pii pair<int,int>
#define fi first
#define se second
#define FILE(x) freopen(x".in","r",stdin);\
	freopen(x".out","w",stdout);
#define pb push_back

int read(){
	int x = 0,sgn = 1;char ch = getchar();
	for(;!isdigit(ch);ch = getchar()) if(ch == '-') sgn = -1;
	for(;isdigit(ch);ch = getchar()) x = (x<<1)+(x<<3)+(ch^48);
	return x*sgn;
}

const int MAXN = 3e5+10;
const int N = 2e4+10;

int ch[MAXN][26],val[MAXN],v[MAXN<<2],lz[MAXN<<2],en[MAXN],fail[MAXN],dfn[MAXN],ddfn[MAXN],tot,tim,nd[MAXN],n;
string s[N];
vector <int> G[MAXN];

void insert(string s,int num){
	int ls = s.size(),p = 1;
	for(int i = 0;i < ls;i++){
		if(!ch[p][s[i]-'a']) ch[p][s[i]-'a'] = ++tot;
		p = ch[p][s[i]-'a'];
	} en[p] = num; nd[num] = p;
}

void getfail(){
	queue<int> q; for(int i = 0;i < 26;i++) ch[0][i] = 1; q.push(1);
	while(q.size()){
		int x = q.front(); q.pop(); int F = fail[x];
		for(int i = 0;i < 26;i++){
			int y = ch[x][i];
			if(!y) ch[x][i] = ch[F][i];
			else fail[y] = ch[F][i],q.push(y);
		}
	}
}

void dfs(int x){
	dfn[x] = ++tim;
	for(int y : G[x]) dfs(y);
	ddfn[x] = tim;
}

void pushdown(int o){
	if(lz[o]){
		lz[o<<1] = max(lz[o<<1],lz[o]); lz[o<<1|1] = max(lz[o<<1|1],lz[o]);
		v[o<<1] = max(v[o<<1],lz[o]); v[o<<1|1] = max(v[o<<1|1],lz[o]);
		lz[o] = 0;
	}
}

void update(int xl,int xr,int val,int o = 1,int l = 1,int r = tot){
	if(xl == l && xr == r){lz[o] = max(lz[o],val);v[o] = max(v[o],val);return;}
	int mid = (l+r)>>1; pushdown(o);
	if(xr <= mid) update(xl,xr,val,o<<1,l,mid);
	else if(xl > mid) update(xl,xr,val,o<<1|1,mid+1,r);
	else update(xl,mid,val,o<<1,l,mid),update(mid+1,xr,val,o<<1|1,mid+1,r);
	v[o] = max(v[o<<1],v[o<<1|1]);
}

int query(int pos,int o = 1,int l = 1,int r = tot){
	if(l == r) return v[o];
	int mid = (l+r)>>1;pushdown(o);
    if(pos <= mid) return query(pos,o<<1,l,mid); else return query(pos,o<<1|1,mid+1,r);
}

int getans(int x){
	int p = 1,res = 0,ls = s[x].size();
	for(int i = 0;i < ls;i++){
		p = ch[p][s[x][i]-'a'];
		res = max(res,query(dfn[p]));
	} return res;
}

int main (){
#ifndef ONLINE_JUDGE
	freopen("1.in","r",stdin);
#endif
	int test = in;
	for(int ttest = 1;ttest <= test;ttest++){
		n = in; tot = 1; tim = 0; memset(ch,0,sizeof(ch));
		for(int i = 1;i <= n;i++) {
			cin>>s[i]; val[i] = in;
			insert(s[i],i);
		}
		getfail(); for(int i = 1;i <= tot;i++) G[i].clear();
		for(int i = 2;i <= tot;i++) G[fail[i]].pb(i);
		dfs(1); memset(v,0,sizeof(v)); memset(lz,0,sizeof(lz));
		int ans = 0;
		for(int i = 1;i <= n;i++){
			int tans = getans(i) + val[i];
			update(dfn[nd[i]],ddfn[nd[i]],tans); ans = max(ans,tans);
		}
		printf("Case #%d: %d\n",ttest,ans);
	}
	return 0;
}

